/*
 *顺序栈的实现及功能
 *@author 寇戈
 *@version 1.0 , 2021-10-12
 */
#include <iostream>
#include <malloc.h>
#include <math.h>
#include "myhead.h"

using namespace std;

#define STACK_INIT_SIZE 100
#define STACK_INCREAMENT 10

typedef struct
{

    //栈的结构
    ElemType *base;
    ElemType *top;
    int stackSize;

    int stackLength_dev; //仅开发时使用
} SqStack;

Status InitStack(SqStack &S)
{
    /*
     * 顺序栈的初始化
     * T(n)=O(1)
     */

    S.base = (ElemType *)malloc(sizeof(ElemType) * STACK_INIT_SIZE);
    if (!S.base)
        exit(OVERFLOW);
    S.top = S.base;
    S.stackSize = STACK_INIT_SIZE;

    S.stackLength_dev = 0;
    return OK;
}

bool StackEmpty(SqStack S)
{
    /*
     * 判断栈是否为空
     * T(n)=O(1)
     */

    if (S.top == S.base)
        return true;
    return false;
}

Status GetTop(SqStack S, ElemType &e)
{
    /*
     * 获取栈顶元素
     * T(n)=O(1)
     */

    if (StackEmpty(S))
        return ERROR;
    e = *(S.top - 1);
    return OK;
}

ElemType GetTop(SqStack S)
{
    /*
     * 获取栈顶元素
     * T(n)=O(1)
     */

    if (StackEmpty(S))
        exit(ERROR);
    return *(S.top - 1);
}

Status Push(SqStack &S, ElemType e)
{
    /*
     * 入栈
     * T(n)=O(1)
     */

    if (S.top == S.base + S.stackSize)
    {
        S.base = (ElemType *)realloc(S.base, sizeof(ElemType) * STACK_INCREAMENT);
        if (!S.base)
            exit(OVERFLOW);
        S.top = S.base + S.stackSize;
        S.stackSize += STACK_INCREAMENT;
    }

    *S.top = e;
    S.top++;

    S.stackLength_dev++;
    return OK;
}

Status Pop(SqStack &S, ElemType &e)
{
    /*
     * 出栈
     * T(n)=O(1)
     */

    if (StackEmpty(S))
        return ERROR;
    e = *--S.top;

    S.stackLength_dev--;
    return OK;
}
ElemType Pop(SqStack &S)
{
    /*
     * 出栈
     * T(n)=O(1)
     */

    if (StackEmpty(S))
        return ERROR;
    ElemType e = *--S.top;

    S.stackLength_dev--;
    return e;
}

Status ClearStack(SqStack &S)
{
    S.top = S.base;
    S.stackLength_dev = 0;
    return OK;
}

Status ShowStack_dev(SqStack S)
{
    /*
     * 查看栈内所有元素(仅开发时使用)
     * T(n)=O(n)
     */

    if (StackEmpty(S))
    {
        cout << "栈为空\n";
        return OK;
    }

    cout << "栈内元素从栈底到栈顶依次为:";
    for (int i = 0; i < S.stackLength_dev; i++)
        cout << *(S.base + i) << " ";
    cout << endl;
    return OK;
}

const char LEFT_BRACKET[3] = {'(', '[', '{'};
const char RIGHT_BRACKET[3] = {')', ']', '}'};

int isLeftBracket(char c)
{
    for (int i = 0; i < 3; i++)
        if (c == LEFT_BRACKET[i])
            return i;
    return -1;
}
int isRightBracket(char c)
{
    for (int i = 0; i < 3; i++)
        if (c == RIGHT_BRACKET[i])
            return i;
    return -1;
}
bool matchJudge(string expression)
{
    /*
     * 利用栈判断括号是否闭合
     *
     * 思路:
     * 遇见左字符，将左字符入栈
     * 遇见右字符：
     *	如果栈是空的，说明括号无效
     *	如果栈不为空，将栈顶字符出栈，与右字符之匹配
     *		如果左右字符不匹配，说明括号无效
     *		如果左右字符匹配，继续扫描下一个字符
     * 所有字符扫描完毕后：
     *	栈为空，说明括号有效
     *	栈不为空，说明括号无效
     *
     */

    SqStack op;
    InitStack(op);

    int i = 0;
    ElemType e;
    while (i < expression.size())
    {
        e = expression[i];
        if (isLeftBracket(e) != -1)
            Push(op, e);
        if (isRightBracket(e) != -1)
        {
            if (StackEmpty(op))
                return false;
            ElemType outer;
            Pop(op, outer);
            if (isLeftBracket(char(outer)) != isRightBracket(e))
                return false;
        }
        i++;
    }
    if (StackEmpty(op))
        return true;
    return false;
}

string decConversion(int dec, int numSys)
{
    /*
     * 进制转换
     * 将输入的十进制数转换为1-10,16进制
     * params:
     *   dec:要转化的十进制数
     *   numSys:要转换的进制,可选的值:2-36;
     */

    if (numSys > 36 && numSys <= 1)
        return "ERROR";
    SqStack S;
    InitStack(S);
    int num;
    string rst;

    while (dec)
    {
        Push(S, dec % numSys);
        dec /= numSys;
    }

    while (!StackEmpty(S))
    {
        Pop(S, num);
        rst += char(num < 9 ? '0' + num : 55 + num);
    }
    return rst;
}

Status lineEdit()
{
    /*
     * 行编辑程序:'#'表示退格,'@'表示退行,'$'停止测试
     */
    SqStack Line;
    InitStack(Line);
    char c = getchar();
    ElemType outer;
    // while (c != EOF)
    while (c != '$')
    {
        switch (c)
        {
        case '#':
            Pop(Line, outer);
            break;
        case '@':
            ClearStack(Line);
            break;
        case '\n':
            for (int i = 0; i < Line.stackLength_dev; i++)
                cout << (char)*(Line.base + i);
            cout << endl;
            ClearStack(Line);
            break;
        default:
            Push(Line, c);
            break;
        }
        c = getchar();
        return OK;
    }
    return OK;
}

int OpCmp(char operator1, char operator2)
{
    /*
     *功能:	判断两个操作符的优先级
     *参数:	operator1--操作符1
     *		operator2--操作符2
     *返回:	操作符1优先级大于操作符2	--LEVEL_BIGGER
     *		操作符1优先级小于操作符2	--LEVEL_SMALLER
     *		操作符1优先级等于操作符2	--LEVEL_SAME
     *		操作符1操作符2对比不合法	--LEVEL_INVALID
     *其他:	2014/04/17 By Jim Wen Ver1.0
     *说明:	这里'+'和'-'，'*'和'/'在实际四则运算时的优先顺序
     *		是相同的,所以这里的优先级判定时设置两个操作符级别
     *		列表,一个操作符列表是把另一个操作符级别列表中的相
     *		同级别的操作符的顺序做了颠倒
     */
#define LEVEL_BIGGER 1
#define LEVEL_SMALLER -1
#define LEVEL_SAME 0
#define LEVEL_INVALID -2

    char levelTable1[] = {'#', '(', '+', '-', '*', '/', ')'};
    char levelTable2[] = {'#', ')', '-', '+', '/', '*', '('};
    int nTable1Index1, nTable1Index2;
    int nTable2Index1, nTable2Index2;

    //不合法情况判断
    if ((operator1 == ')' && operator2 == '(') ||
        (operator1 == '#' && operator2 == ')') ||
        (operator1 == '(' && operator2 == '#'))
    {
        return LEVEL_INVALID;
    }

    //判断相等情况
    if ((operator1 == '(' && operator2 == ')') ||
        (operator1 == '#' && operator2 == '#'))
    {
        return LEVEL_SAME;
    }

    //判断两个操作符在两个优先级表中的位置
    nTable1Index1 = nTable1Index2 = -1;
    nTable2Index1 = nTable2Index2 = -1;

    while (levelTable1[++nTable1Index1] != operator1)
        ;
    while (levelTable1[++nTable1Index2] != operator2)
        ;
    while (levelTable2[++nTable2Index1] != operator1)
        ;
    while (levelTable2[++nTable2Index2] != operator2)
        ;

    // 1.判断两个操作符的优先级关系
    // 2.'#' < '+', '-' < '*', '/'
    // 3.两个相同的运算符或同级别的运算符('+'和'-'，'*'和'/')
    //对比时应判定为前一个运算符优先级别高,这样才能保证连续
    //两个相同的运算符或同级别的运算符出现时前一个运算符出栈
    //完成一次计算
    if (nTable1Index1 - nTable1Index2 < 0 && nTable2Index1 - nTable2Index2 < 0 ||
        operator1 == '(' ||
        operator2 == '(')
    {
        return LEVEL_SMALLER;
    }
    else
    {
        return LEVEL_BIGGER;
    }
}

bool IsOp(char c)
{
    /*
     *功能:	判断字符是否属于基本四则运算符号
     */
    const string ops = "+-*/()#";
    for (int i = 0; i < ops.length(); i++)
        if (c == ops[i])
            return true;
    return false;
}
int CalculateUnit(double num1, double num2, char op)
{
    /*
     *功能:	计算的核心函数
     */
    switch (op)
    {
    case '+':
        return num1 + num2;
    case '-':
        return num1 - num2;
    case '*':
        return num1 * num2;
    case '/':
        return num1 / num2;
    default:
        return 0;
    }
}

int Calculate(string expression)
{
    /*
     *功能:	计算表达式
     */
    expression += '#';
    SqStack OPND, OPTR;
    InitStack(OPND);
    InitStack(OPTR);
    Push(OPTR, '#');
    int i = 0;
    char c = expression[i];
    int flag = 0;

    while (c != '#' || GetTop(OPTR) != '#')
    {
        c = expression[i];
        if (!IsOp(c))
        {
            int num = int(c - '0');
            if (flag)
                num += Pop(OPND) * pow(10, flag);
            Push(OPND, num);
            i++;
            flag++;
        }
        else
        {
            flag = 0;
            switch (OpCmp(GetTop(OPTR), c))
            {
            case LEVEL_SMALLER:
                Push(OPTR, c);
                i++;
                break;
            case LEVEL_SAME:
                Pop(OPTR);
                i++;
                break;
            case LEVEL_BIGGER:
                Push(OPND, CalculateUnit(Pop(OPND), Pop(OPND), Pop(OPTR)));

                break;
            default:
                break;
            }
        }
    }
    return GetTop(OPND);
}

string toSuffix(string expression)
{
    expression += '#';
    string suffix = "";
    SqStack OPTR;
    InitStack(OPTR);
    Push(OPTR, '#');
    int i = 0;
    char c = expression[i];
    while (c != '#' || GetTop(OPTR) != '#')
    {
        c = expression[i];
        if (!IsOp(c))
        {
            suffix += c;
            i++;
        }
        else
        {
            if (c == ')')
            {
                while (GetTop(OPTR) != '(')
                    suffix += Pop(OPTR);
                Pop(OPTR);
                i++;
            }
            else
                switch (OpCmp(GetTop(OPTR), c))
                {
                case LEVEL_SMALLER:
                    Push(OPTR, c);
                    i++;
                    break;
                case LEVEL_BIGGER:
                    suffix += (char)Pop(OPTR);
                    Push(OPTR, c);
                    i++;
                    break;
                default:
                    break;
                }
        }
    }
    return suffix;
}

Status ReverseStr(string str)
{
    SqStack S;
    InitStack(S);
    int i = 0;
    while (i < str.size())
    {
        Push(S, str[i]);
        i++;
    }
    while (!StackEmpty(S))
    {
        int e;
        Pop(S, e);
        cout << (char)e;
    }
    return OK;
}

// Status Test_dev(SqStack &S)
// {
//     /*
//      * 栈的操作测试(仅开发时使用)
//      */
//     cout << "请选择操作：1.入栈测试\n2.出栈测试\n3.获取栈顶元素测试\n4.清空栈测试\n5.括号匹配测试\n6.进制转化测试\n7.行编辑测试\n8.计算运算表达式测试\n9.中缀表达式转后缀\n0.逆序输出字符串\nf.停止测试\n\n";
//     char op;
//     ElemType e = 0;
//     string expression;
//     string rst;
//     int dec, numSys;
//     string str;

//     cin >> op;
//     switch (op)
//     {
//     case '1':
//         cout << "请输入要入栈的元素：\n";
//         cin >> e;
//         Push(S, e);
//         ShowStack_dev(S);
//         break;
//     case '2':
//         if (!Pop(S, e))
//             cout << "无法弹出,因为";
//         else
//             cout << "弹出的元素" << e << endl;
//         ShowStack_dev(S);
//         break;
//     case '3':
//         if (GetTop(S, e))
//             cout << "栈顶元素为：" << e << endl;
//         else
//             cout << "无法获取栈顶元素,因为";
//         ShowStack_dev(S);
//         break;
//     case '4':
//         ClearStack(S);
//         ShowStack_dev(S);
//         break;
//     case '5':
//         cout << "请输入表达式:" << endl;
//         cin >> expression;
//         rst = matchJudge(expression) ? "括号匹配\n" : "括号不匹配\n";
//         cout << rst;
//         break;
//     case '6':
//         cout << "请输入要转化的十进制数:" << endl;
//         cin >> dec;
//         cout << "请输入要转化进制(2-36):" << endl;
//         cin >> numSys;
//         cout << "十进制数" << dec << "转化为" << numSys << "进制为:" << decConversion(dec, numSys) << endl;
//         break;
//     case '7':
//         lineEdit();
//         break;
//     case '8':
//         cout << "请输入算数表达式:\n";
//         cin >> expression;
//         cout << Calculate(expression) << endl;
//         break;

//     case '9':
//         cout << "请输入算数表达式:\n";
//         cin >> expression;
//         cout << toSuffix(expression) << endl;
//         break;
//     case '0':
//         cout << "请输入字符串:\n";
//         cin >> str;
//         cout << "逆序:";
//         ReverseStr(str);
//         cout << endl;
//         break;
//     case 'f':
//         exit(OK);
//         break;
//     default:
//         break;
//     }
//     return OK;
// }

// int main()
// {

//     SqStack S1;

//     //初始化栈测试
//     InitStack(S1);

//     //栈的操作测试
//     while (true)
//         Test_dev(S1);
//     return 0;
// }